package com.dangdang.recursion;

import com.dangdang.binarytree.Node;

import java.util.Stack;

public class Traverse {

    //递归遍历
    public static void recursionTraverse(Node tree){
        if (tree == null) {
            return;
        }

        recursionTraverse(tree.getLeft());
        System.out.println(tree.getValue());
        recursionTraverse(tree.getRight());
    }

    //利用栈遍历
    public static void stackTraverse(Node tree){

        Stack<Node> stack = new Stack<>();
        Node node = tree;

        while (node != null || !stack.isEmpty()) {
            while (node != null) {
                stack.push(node);
                node = node.getLeft();
            }
/*            if (!stack.isEmpty()) {
                node = stack.pop();
                System.out.println(node.getValue());
                node = node.getRight();
            }*/

            node = stack.pop();
            System.out.println(node.getValue());
            node = node.getRight();

        }

    }

    public static void main(String[] args) {
        Node node = new Node();
        Node.generate(node);

        //Traverse.recursionTraverse(node);
        Traverse.stackTraverse(node);

    }
}
